'''
https://leetcode.cn/problems/count-good-numbers/description
'''
import math

MOD = 10 ** 9 + 7
class Solution:
    def countGoodNumbers(self, n: int) -> int:
        if n == 1: return 5
        res = 5
        for i in range(1, n):
            if i & 1:
                res = (res * 4) % MOD
            else:
                res = (res * 5) % MOD
        return res

    # 归并
    def countGoodNumbers2(self, n: int) -> int:
        def f(l, r):
            if l > r:
                return 1
            if l == r:
                return 4 if l & 1 else 5
            mid = l + r >> 1
            left_ans = f(l, mid)
            right_ans = f(mid + 1, r)
            return left_ans * right_ans % MOD
        return f(0, n-1)

    # 快速幂
    def countGoodNumbers3(self, n: int) -> int:
        return pow(5, (n+1) // 2, MOD) * pow(4, n // 2, MOD) % MOD

n = 806166225460393
print(math.log2(806166225460393))
obj = Solution()
# for i in range(1, 10):
#     r1 = obj.countGoodNumbers2(i)
#     r2 = obj.countGoodNumbers3(i)
#     print(i, r1, r2)
print(obj.countGoodNumbers3(n))
print(obj.countGoodNumbers2(n))
